﻿#include <stdio.h>
#include <stdbool.h>
void print(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}
//插入排序
void InsertSort(int* a,int n)
{
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int tmp = a[i];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
				break;
		}
		a[end + 1] = tmp;
	}
}
//希尔排序
void ShellSort(int* a, int n)
{
	int gap = n / 2;
	while (gap > 0)
	{
		for (int i = 1; i < n + 1 - gap; i++)
		{
			int end = i - 1;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = tmp;
		}
		gap /= 2;
	}
}
int main()
{
	int a[] = { 3,2,5,7,7,1,6,8,0 };
	int size = sizeof(a) / sizeof(a[0]);
	ShellSort(a, size);
	print(a, size);
	return 0;
}